package offer;

/**
 * @Author Elephas
 * @Date 2022/3/18
 **/
public interface Exists {
    boolean exist(char[][] board, String word);
}

class ExistsTest {

    public static void main(String[] args) {

    }
}

class ExistsImpl1 implements Exists{
    private char[][] board;
    private int m;
    private int n;
    static final int[][] dirs = new int[][] {{-1,0},{1,0},{0,1},{0,-1}};
    @Override
    public boolean exist(char[][] board, String word) {
        this.board = board;
        m = board.length;
        n = board[0].length;
        // ordinary case
        if(word.length() == 1){
            char ch = word.charAt(0);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if(board[i][j] == ch){
                        return true;
                    }else{
                        return false;
                    }
                }
            }
        }
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                visited[i][j] = false;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int cur = 0;
                if(dfs(visited, board, i, j, word, cur)){
                    return true;
                }
            }
        }
        return false;
    }
    private boolean isValidIndexes(boolean[][] visited, int i, int j){
        if(i >= 0 && i < m && j >= 0 && j < n && !visited[i][j]){
            return true;
        }else{
            return false;
        }
    }
    private boolean dfs(boolean[][] visited, char[][] board, int i, int j, String word, int cur){
        if(cur == word.length()){
            return true;
        }else{
            char ch = word.charAt(cur);
            if(isValidIndexes(visited, i, j) && board[i][j] == ch){
                visited[i][j] = true;
                for(int[] dir : dirs){
                    if(dfs(visited, board, i + dir[0], j + dir[1], word, cur + 1)){
                        return true;
                    }
                }
                visited[i][j] = false;
            }
            return false;
        }
    }
}
